package com.example.algorithm.no0337.impl;

import com.example.algorithm.no0337.Solution;
import com.example.algorithm.no0337.TreeNode;

/**
 * @author yumuhui <yumuhui@kuaishou.com>
 * Created on 2021-05-13
 */
public class ArraySolutionImpl implements Solution {

    @Override
    public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }

    public int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int selected = node.val + left[1] + right[1];
        int unSelected = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{selected, unSelected};
    }

}
